关于RSA公钥系统和DSA、ESIGN签名算法

（IC卡教材中的部分章节学习笔记 皮可慰）

（2000年）

 

密码系统的研究是一个历史悠久的课题，传统的密码系统要求通讯双方保存唯一的加密和解密钥，而加密和解密钥都必须保持机密，尤其是他们的传递过程必须通过非公开通讯讯道来进行，这就使得一一对应的加密和解密钥的数量庞大，保存和传递非常困难。自从80年代发明了非对称公钥系统后，情况发生了飞跃，再不需要一一对应的“密码薄”了，加密钥和加密方法可以公布于众，而破解的可能性降为零，同时使得“电子签名”成为了可能。

 

一、建立和运用公钥加密系统的步骤（以RSA为例）

1、         选择两个素数：P 和Q，如3 和 5 ，（实际要大得多）

2、         求N=P*Q=3*5=15

3、         计算欧拉函数F（N）=（P-1）（Q-1）=（3-1）（5-1）=8

4、         另选一个与F（N）互素的整数E为公开的加密密钥，

设本例选

E=11

5、         求解密密钥D

D必须满足下式：  D*E=K（P-1）（Q-1）+1

其中K为整数

        本例 D*11=K（P-1）（Q-1）+1

D*11=K*8+1

D=（K*8+1）/11

          试当K=1时，D不是整数；当K=2时，D也不是整数；

          直到K=4时，D=3

          即本例的解密密钥为3

6、         公布加密密钥及加密算法：

加密密钥E=11

加密算法 密码=明码的E次方除以N之后的余数

   即C=M（E） MOD N

   即C=明码的11次方，除以15 之后的余额。

如明码为7，

则C=711/15的余数=72*72*72*72*72*7的余数=49*49*49**49*49*7的余数=4*4*4*4*4*7的余数=13

 即密码为13。

7、         收到密码后，用保密的密钥（本例为3）解密：

还原明码=密码的D次方，除以N之后的余额

 如密码为13

 则  M=13的3次方，除以15之后的余额=7

即明码还原为7。

同样可以计算若明码为2时，密码为8。

当密码为8时，可以还原明码为2。

    8、但是，由于原文与密文是一一对应的，尽管人们不知道密钥，但如上例可以知道明码的7、2，一一对应于密码的13和8；时间长了总会被破译，如何解决这个问题呢？

解决的办法是取N足够大，每一加密单位（即分组）可以大到无法猜测的地步，即可防止泄密。如“我”对应于23，“们”对应于27，显然2327即为“我们”，这是容易破译的；但如果“我们的工作”对应于2327455634，而“我们的学习”对应于3245678909，那就无法破译了。

 

二、签名算法问题：

1、        RSA的解决办法：

签名者A设置一套密制，自己保留密钥，同时将加密钥公开

给核实者B（当然也可以是无数的公众），当A使用密钥将一段文字“反解密”（成为不可识别的“明文”）交给核实者B，则B可使用加密密钥将此文译为有意义的文字（成为可以识别的“密码”，），以证明A的身份是有效的。而A也无法否认自己的“签字”，因为任何人无法用A自己给出的加密密钥创造出一段有意义的文字。

这种方法不需要预留“密码”， 无法由计算机核对签字的正确性，且计算量大，对于类似信用卡来说不太适用。

2、美国的DSA签名法要点：签名者A掌握提交的密文M及秘密密钥X，接收者B掌握公开密钥Y和素数P、Q以及对方提交的由密文M计算出的G。

 签名过程：由签名者A输入M，按照特定算法产生R及S，传输给接收者B；

 验证过程：接收者B根据已掌握的公开密钥Y和素数P、Q，对签名者A本次提交的R及S， 以特定的算法计算，并与A事先提交的由密文M计算出的G比较。

由于B始终不知道A预留的密码M，只预留由M计算出的G，以及本次的M也要转换为R及S再提交给B核对，因此保证了M的保密性。

与RSA的区别是需要预留密码，以便有一个核对过程，让计算机能自行判断。但并不是直接将密码M留下来，而是将其用非常简单的方法转换成的核对标尺G，核对时也不是直接核对密码M，而是将签名的密码M用简单的方法转化为R、S再与G核对即可。

2、         日本的SIGN签名法要点：与DSA大同小异，不再叙述。

 

三、数学对密码学的贡献

上述RSA公钥系统和签名算法能够成为现实，一个重要的原因是充分利用了某些数学计算的反向过程难度太大的特性，如两个很大的素数相乘是非常容易做到的，但要将这样积数分解成两个因数则非常难，当单个素数大到上百位时几乎是利用计算机都无法分解的了；又如微分过程相对容易实现，而各积分计算则难度大得多。

上述RSA由公开的密钥将明文加密成密文相对容易，而反向由密文通过公开的密钥还原为明文，由于计算难度大几乎是不可能的，只有通过密钥才能解密，而加密钥和密钥是同时通过计算形成的，但形成之后再想找出它们之间的关系又是非常困难的了。

又如上述DSA签名算法也是一样。在留签过程，由留存签名转换为核对标尺G是非常容易实现的，而反过来由核对标尺G转化为留存签名则是非常困难的，这就使得保留留存签名的核对者或者其他人根本无法模仿留存签名； 在验证过程，由现场签名转化为用以和留在核对者手中的标尺G核对的数据R、S是容易实现的，而反过来由R、S转化为现场签名又是非常困难的，这就使得模仿和破译成为不可能。

 

                      皮可慰   2000年3月25日